package com.coder.algorithm.offer_2;

/**
 * 复杂链表的复制
 *
 * @author yuhushuan
 * @date 2020/6/22 10:46
 */
public class _35_1_CopyComplexList {

    static class ComplexListNode {
        int value;
        ComplexListNode next;
        ComplexListNode sibling;

        public static String toString(ComplexListNode node) {
            if (node == null) {
                return "null";
            }
            StringBuilder sb = new StringBuilder();
            StringBuilder extra = new StringBuilder();

            sb.append('[');
            while (node != null) {
                sb.append(node.value);
                if (node.next != null) {
                    sb.append(", ");
                }

                extra.append('[').append(node.value).append(", ");
                if (node.sibling != null) {
                    extra.append(node.sibling.value);
                } else {
                    extra.append("null");
                }
                extra.append("]\n");

                node = node.next;
            }
            sb.append("]\n").append(extra.toString());
            return sb.toString();
        }
    }

    private static ComplexListNode cloneNodes(ComplexListNode head) {
        if (head == null) {
            return null;
        }
        // 第一步 克隆节点并置于节点之后，完成后链表长度为 2n
        ComplexListNode node = head;
        ComplexListNode cloneNode;
        while (node != null) {
            cloneNode = new ComplexListNode();
            cloneNode.value = node.value;
            cloneNode.next = node.next;
            cloneNode.sibling = null;

            node.next = cloneNode;
            node = cloneNode.next;
        }

        // 第二步 对 sibling 指针赋值
        node = head;
        while (node != null) {
            cloneNode = node.next;
            if (node.sibling != null) {
                cloneNode.sibling = node.sibling.next;
            }
            node = cloneNode.next;
        }

        // 第三步 拆分克隆链表
        ComplexListNode cloneHead = head.next;
        node = head;
        while (node != null) {
            cloneNode = node.next;

            node.next = cloneNode.next;
            node = cloneNode.next;

            if (node == null) {
                cloneNode.next = null;
            } else {
                cloneNode.next = node.next;
            }
        }
        return cloneHead;
    }

    public static void main(String[] args) {
        ComplexListNode n1 = new ComplexListNode();
        n1.value = 1;
        ComplexListNode n2 = new ComplexListNode();
        n2.value = 2;
        ComplexListNode n3 = new ComplexListNode();
        n3.value = 3;
        ComplexListNode n4 = new ComplexListNode();
        n4.value = 4;
        ComplexListNode n5 = new ComplexListNode();
        n5.value = 5;

        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = null;

        // 功能测试
        // 节点中的 sibling 指向节点自身
        n1.sibling = n1;
        n2.sibling = n2;
        n3.sibling = n3;
        n4.sibling = n4;
        n5.sibling = n5;
        print(n1);

        // 两个节点的 sibling 形成环状结构
        n1.sibling = n2;
        n2.sibling = n1;
        n3.sibling = n3;
        n4.sibling = n4;
        n5.sibling = n5;
        print(n1);
        // 链表中只有一个节点
        n1.next = null;
        n1.sibling = null;
        print(n1);

        // 特殊输入测试 null
        print(null);
    }

    private static void print(ComplexListNode head) {
        System.out.println("链表为：\n" + ComplexListNode.toString(head));
        System.out.println("复制后的链表为：\n" + ComplexListNode.toString(cloneNodes(head)));
    }


}
